from typing import List


# 64. 最小路径和
# 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
def minPathSum(grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    # dp 数组第一行
    for row_index in range(1, n + 1):
        dp[1][row_index] = dp[1][row_index - 1] + grid[0][row_index - 1]
    # dp 数组第一列
    for column_index in range(1, m + 1):
        dp[column_index][1] = dp[column_index - 1][1] + grid[column_index - 1][0]
    # dp 数组
    # 遍历行
    for row in range(2, m + 1):
        # 遍历列
        for column in range(2, n + 1):
            dp[row][column] = (min(dp[row][column - 1], dp[row - 1][column])
                               + grid[row - 1][column - 1])

    return dp[m][n]


grid_1 = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
result = minPathSum(grid_1)
print(f"result:{result}")

grid_1 = [[1, 2, 3], [4, 5, 6]]
result = minPathSum(grid_1)
print(f"result:{result}")
